AES 和 RSA 笔记

Posted on   |   In   |     |  

简单回顾 AES 和 RSA 算法。

Symmetric key 对称加密

加密和解密均采用同一把密钥，而且通信双方都必须获得这把密钥。一方通过密钥将信息加密后，把密文传给另一方，另一方通过这个相同的密钥将密文解密，转换成可以理解的明文。
常见的对称加密算法有DES、3DES、AES、Blowfish、IDEA、RC5、RC6、AES。

  • DES（Data Encryption Standard）：数据加密标准，速度较快，适用于加密大量数据的场合。
  • 3DES（Triple DES）：是基于DES，对一块数据用三个不同的密钥进行三次加密，强度更高。
  • AES（Advanced Encryption Standard）：高级加密标准，是下一代的加密算法标准，速度快，安全级别高；

对称加密的最大优点是速度快，然而它也存在着诸多问题。

存在问题

  • 要求提供一条安全的渠道使通讯双方在首次通讯时协商一个共同的密钥。直接的面对面协商可能是不现实而且难于实施的，所以双方可能需要借助于邮件和电话等其它相对不够安全的手段来进行协商；
  • 密钥的数目难于管理。因为对于每一个合作者都需要使用不同的密钥，很难适应开放社会中大量的信息交流；而如果大家都使用同一个密钥，只要其中一个人密钥被盗窃了，那么整体加密的信息将都被破解了。
  • 对称加密算法一般不能提供信息完整性的鉴别。它无法验证发送者和接受者的身份。
  • 对称密钥的管理和分发工作是一件具有潜在危险的和烦琐的过程。对称加密是基于共同保守秘密来实现的，采用对称加密技术的贸易双方必须保证采用的是相同的密钥，保证彼此密钥的交换是安全可靠的，同时还要设定防止密钥泄密和更改密钥的程序。

AES


AES加密过程涉及到4种操作：字节替代（SubBytes）、行移位（ShiftRows）、列混淆（MixColumns）和轮密钥加（AddRoundKey）。从上图可以看出：1）解密过程的每一步分别对应操作的逆操作，2）加解密所有操作的顺序正好是相反的。正是由于这两点保证了解密能够正确地恢复明文。加解密中每轮的密钥分别由初始密钥扩展得到。算法中16字节的明文、密文和轮密钥都以一个4x4的矩阵表示。

算法详解

Asymmetric key 非对称加密

使用非对称加密算法，首先要有一对key，一个是private key私钥，另一个是public key公钥，如果用公开密钥对数据进行加密，只有用对应的私有密钥才能解密；如果用私有密钥对数据进行加密，那么只有用对应的公开密钥才能解密。因为加密和解密使用的是两个不同的密钥，所以这种算法叫作非对称加密算法。可以把你的public key分发给想给你传密文的用户，然后用户使用该public key加密过的密文，只有使用你的 private key 才能解密，也就是说，只要你自己保存好你的 private key，就能确保，别人想给你发的密文不被破解，所以你不用担心别人的密钥被盗。

过程：

  1. 乙方生成两把密钥（公钥和私钥）。公钥是公开的，任何人都可以获得，私钥则是保密的。
  2. 甲方获取乙方的公钥，然后用它对信息加密。
  3. 乙方得到加密后的信息，用私钥解密。

非对称加密算法对 symmetric key 进行了加密，保密性比较好，它消除了最终用户交换密钥的需要，而且能提供长期的 signatures。但加密和解密花费时间长、速度慢，在某些极端情况下，甚至能比非对称加密慢上1000倍。因此它不适合于对文件加密而只适用于对少量数据进行加密。

举个例子，如果企业中有n个用户，企业需要生成n对密钥，并分发n个公钥。由于公钥是可以公开的，用户只要保管好自己的私钥即可(企业分发后一般保存的是私钥,用户拿的是公钥)，因此加密密钥的分发将变得十分简单。同时，由于每个用户的私钥是唯一的，其他用户除了可以通过信息发送者的公钥来验证信息的来源是否真实，还可以确保发送者无法否认曾发送过该信息。

这种加密算法应用非常广泛，SSH, HTTPS, TLS，电子证书，电子签名，电子身份证等等。

RSA

1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的”非对称加密算法”。毫不夸张地说，只要有计算机网络的地方，就有RSA算法。
这种算法非常可靠，密钥越长，它就越难破解。根据已经披露的文献，目前被破解的最长RSA密钥是768个二进制位。也就是说，长度超过768位的密钥，还无法破解（至少没人公开宣布）。因此可以认为，1024位的RSA密钥基本安全，2048位的密钥极其安全。
代码理解 RSA 算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
/* Demonstrate RSA in Java using BigIntegers */
import java.math.BigInteger;
import java.util.Random;
/**
 *  RSA Algorithm from CLR
 *
 * 1. Select at random two large prime numbers p and q.
 * 2. Compute n by the equation n = p * q.
 * 3. Compute phi(n)=  (p - 1) * ( q - 1)
 * 4. Select a small odd integer e that is relatively prime to phi(n).
 * 5. Compute d as the multiplicative inverse of e modulo phi(n). A theorem in
 *    number theory asserts that d exists and is uniquely defined.
 * 6. Publish the pair P = (e,n) as the RSA public key.
 * 7. Keep secret the pair S = (d,n) as the RSA secret key.
 * 8. To encrypt a message M compute C = M^e (mod n)
 * 9. To decrypt a message C compute M = C^d (mod n)
 */
public class RSAExample {
  public static void main(String[] args) {
    // Each public and private key consists of an exponent and a modulus
    BigInteger n; // n is the modulus for both the private and public keys
    BigInteger e; // e is the exponent of the public key
    BigInteger d; // d is the exponent of the private key
    Random rnd = new Random();
    // Step 1: Generate two large random primes.
    // We use 400 bits here, but best practice for security is 2048 bits.
    // Change 400 to 2048, recompile, and run the program again and you will
    // notice it takes much longer to do the math with that many bits.
    BigInteger p = new BigInteger(400,100,rnd);
    BigInteger q = new BigInteger(400,100,rnd);
    // Step 2: Compute n by the equation n = p * q.
    n = p.multiply(q);
    // Step 3: Compute phi(n) = (p-1) * (q-1)
    BigInteger phi = (p.subtract(BigInteger.ONE)).multiply(q.subtract(BigInteger.ONE));
    // Step 4: Select a small odd integer e that is relatively prime to phi(n).
    // By convention the prime 65537 is used as the public exponent.
    e = new BigInteger ("65537");
    // Step 5: Compute d as the multiplicative inverse of e modulo phi(n).
    d = e.modInverse(phi);
    System.out.println(" e = " + e);  // Step 6: (e,n) is the RSA public key
    System.out.println(" d = " + d);  // Step 7: (d,n) is the RSA private key
    System.out.println(" n = " + n);  // Modulus for both keys
    // Encode a simple message. For example the letter 'A' in UTF-8 is 65
    BigInteger m = new BigInteger("65");
    // Step 8: To encrypt a message M compute C = M^e (mod n)
    BigInteger c = m.modPow(e, n);
    // Step 9: To decrypt a message C compute M = C^d (mod n)
    BigInteger clear = c.modPow(d, n);
    System.out.println("Cypher text = " + c);
    System.out.println("Clear text = " + clear); // Should be "65"
    // Step 8 (reprise) Encrypt the string 'Hello'
    String s = "RSA is way cool.";
    m = new BigInteger(s.getBytes()); // m is the original clear text
    c = m.modPow(e, n);     // Do the encryption, c is the cypher text
    // Step 9 (reprise) Decrypt...
    clear = c.modPow(d, n); // Decrypt, clear is the resulting clear text
    String clearStr = new String(clear.toByteArray());  // Decode to a string
    System.out.println("Cypher text = " + c);
    System.out.println("Clear text = " + clearStr);
  }
}

数学原理参见
RSA算法原理（一）
RSA算法原理（二）

徐阿衡 wechat
欢迎关注：徐阿衡的微信公众号
客官，打个赏呗~